package org.example.sword2offer.primary;


import java.util.Stack;

/**
 *  @author: lynn
 *   @description: 栈的压入、弹出序列
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
 * 假设压入栈的所有数字均不相等
 *   @date: 2021/3/11 14:11
 *   @version 1.0.0
 */
public class Q22_IsPopOrder {

    public static void main(String[] args) {
        int[] arrA={1,2,3,4,5};
        int[] arrB={4,5,3,2,1};
        System.out.println(Boolean.toString(doCheck(arrA,arrB)));
    }


    /**
     *借助一个栈，根据给定的入栈序、出栈序模拟它的过程，看看能不能对的上。具体规则是借助一个栈，
     * 拿着它的入栈序进行入栈，每入一次就看看栈顶元素是不是和它的出栈序一样，一样的话我们也出栈，这里需要循环判断，
     * 即出栈完继续看栈顶元素和它的下一个出栈序一样不，一样继续出栈，不一样继续按照它的入栈序入栈，直到入栈序完，
     * 此时如果我们的辅助栈如果是空的话,说明它给定的入栈序与出栈序可以匹配，因为每一个入栈元素都会根据出栈序全部出栈，否则说明不匹配。
     *
     */
    private static boolean doCheck(int[] arrA,int[] arrB){
        //辅助栈，辅助判断B是否为A的弹出栈
        if (arrA.length!=arrB.length){
            return false;
        }
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for (int i = 0; i <arrA.length; i++) {
            stack.push(arrA[i]);
            while (stack.peek()==arrB[j] ){
                stack.pop();
                j++;
                if (stack.isEmpty()){
                    break;
                }
            }
            if (arrB.length==j){
                return true;
            }

        }
        return false;
    }
}
